package com.bigshen.algorithm.nUnionFind.solution01;

import java.util.HashMap;
import java.util.Map;

// 并查集
public class UnionFind {

    Map<Integer, Integer> parentMap = new HashMap<>();

    public Integer findFather(int x) {
        Integer father = parentMap.get(x);
        while (father != parentMap.get(father)) {
            father = parentMap.get(father);
        }
        return father;
    }

    // 合并
    public Integer union(int x, int y) {

        Integer fa_x = findFather(x);
        Integer fa_y = findFather(y);
        parentMap.put(fa_y, fa_x);
        if (fa_x != fa_y) {
            Integer element = y;
            while (element != parentMap.get(element)) {
                Integer tmp = parentMap.get(element);
                parentMap.put(element, fa_x);
                element = tmp;
            }
        }
        return fa_x;
    }

    public static void main(String[] args) {

        UnionFind union = new UnionFind();

        union.parentMap.put(1,1);
        union.parentMap.put(2,1);
        union.parentMap.put(3,2);
        union.parentMap.put(4,3);
        union.parentMap.put(5,4);
        union.parentMap.put(11,11);
        union.parentMap.put(12,11);
        union.parentMap.put(13,12);
        union.parentMap.put(14,13);
        union.parentMap.put(15,14);

        System.out.println(union.findFather(5));
        System.out.println(union.findFather(15));

        union.union(5,15);

    }

}
